『ARC 092F』Two Faced Edges

Problem

Time limit : 2sec / Memory limit : 256MB

题意：

给定一个有向图，然后询问每一条边将它反转之后整张图的强联通分量是否会发生变化

door♂

Solution

设改变的边 为 $u \rightarrow v$，那么 下列两个条件有且仅有一个成立的时候，答案数量会改变。

$v \rightarrow u $本身是否联通
去掉$u \rightarrow v$这条边之后，$u \rightarrow v$ 可以通过其他方式联通。

• 第一个我们可以开始$O(nm)$直接暴力做，一个做第二个的时候顺便判
• 假设和$x$相连的点为 $y_1 ,y_2 \dots y_k$
• 记录从$x$出发到 $y_i $的所有路径里其中的第一条和最后一条，如果它们都必须经过$x_i \rightarrow y_i$这条边的话，就说明了这条边是一定会被选的。那么就可以对于每个点 $x$， 就从$1$到$k$ 逐个$\text{dfs}$它所连接的每一个$y_i$, 要求不经过$x$
• 若$x \rightarrow y_j$ 在加其他边的时候已经联通了，说明$x \rightarrow y_j$这条边可以不选，接着再倒着从$k$到$1$ 逐个$\text{dfs}$它所连接的每一个$y_i$，如果 $x \rightarrow y_j$在其他边的时候已经联通，同样说明这条边可以不选。
• 如果两次$\text{dfs}$发现，都是在假如$x \rightarrow y_j$的边的时候$x \rightarrow y_j$才联通，那么说明$x \rightarrow y_j$必须选了。 在$\text{dfs}$中我们用$f_{a,b,0/1}$表示从第$a$个点出发，正着或者倒着枚举的时候使得与$b$联通的第一条边即可。

Code:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector> 
#include <string>

using namespace std;
const int MAXN = 1e3 + 10;
struct node
{
	int nxt, id;
	node(int a, int b)
	{
		nxt = a;
		id = b;
	}
	node() {}
};
int n, m, tim;
int vis[MAXN];
int res[MAXN][MAXN][2];
int u[MAXN * MAXN], v[MAXN * MAXN];
vector <node> edge[MAXN];
inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}
inline void dfs(const int &now, const int fa, const int &b, const int &f)
{
	vis[now] = tim;
	res[fa][now][f] = b;
	register int len = edge[now].size();
	for (register int i = 0; i < len; i++)
		if (vis[edge[now][i].nxt] != tim)
			dfs(edge[now][i].nxt, fa, b, f);
}
inline void solve(const int & now)
{
	tim++; vis[now] = tim;
	register int len = edge[now].size();
	for (register int i = 0; i < len; i++)
		if (vis[edge[now][i].nxt] != tim)
			dfs(edge[now][i].nxt, now, edge[now][i].id, 0);

	reverse(edge[now].begin(), edge[now].end());

	vis[now] = ++tim;
	for (register int i = 0; i < len; i++)
		if (vis[edge[now][i].nxt] != tim)
			dfs(edge[now][i].nxt, now, edge[now][i].id, 1);
}
int main(int argc, char **Argv)
{
	_read(n), _read(m);
	for (register int i = 1; i <= m; i++)
	{
		_read(u[i]), _read(v[i]);
		edge[u[i]].push_back(node(v[i], i));
	}
	for (register int i = 1; i <= n; i++)
		solve(i);
	for (register int i = 1; i <= m; i++)
	{
		if ((res[v[i]][u[i]][0] != 0) ^ 0 ^ (res[u[i]][v[i]][0] != i || res[u[i]][v[i]][1] != i))
			puts("diff");
		else
			puts("same");
	}
	return 0;
}